** Problema petitorilor **

- Se dau N pretendenti pt mana printesei , acestia avand P[i] pietrie pretioase fiecare. Ei trebuie sa 
ii mituiasca pe ceilalti pretendenti astfel incat ei sa ramana singurii pretendeti. 
Care este nr de pietre cu care se poate ajung la printesa , stiind ca atunci cand petiroul [i] il 
mituieste pe [i-1] sau [i+1] ii ofera P[i-1] / P[i+1] pietre (dupa caz) ?

Folosim programarea dinamica in felul urmator. Fie o matrice [i][j] de liste [j2] care 
retine nr. de pietre ale unui petitor dupa fiecare petire posibila. 

Complexitatea este O(N ^ 3) - neoptim.

			<-----------

Mat | 8  | 1  | 7  | 2  | 3  |
____|____|____|____|____|____|
8   | 8  | 7  | 2,0| 0,3|5,3,|
    |	 |    |	   |	|7,1 |
____|____|____|____|____|____|
1   |    | 1  | 6  | 4  |    |
____|____|____|____|____|____|
7   |    |    | 7  | 5  | 6,2|
____|____|____|____|____|____|
2   |    |    |    | 2  | 1  |  ^
____|____|____|____|____|____|  |
3   |    |    |    |    |  3 |  |
____|____|____|____|____|____|  |


 List(Mat[i][j]) = | Abs ( List(Mat[j][j]) - List(Mat[j-1][i]) ) ;
                   | Abs ( List(Mat[j-1][j]) - List(Mat[j-2][i]) ) ;
				   |          .......
				   | Abs ( List(Mat[i+1][j]) - List(Mat[1][i]) ) ;

** Problema triangularii **
 Se da un poligon cu N laturi. Se cere sa se determine suma minima a lungimilor dreptelor care
 impart pligonul intr-un triunghi.
 
 Recurenta este :
 T(1,N)=minim( P(1,vf,N) + T(1,vf) + T(vf,N) ) , unde P(x,y,z) este perimetrul determinat de pnct. x,y,z ;
 
 Initializare : T[1][1]=0,T[1][2]=0; T[2][2]=0,T[2][3]=0; ... T[N][N]=0 (T[N][N+1]=0) ;
 
 Tabel dinamic:
    MAT | 	1| 	2 | 3	   | 4	    | 5	     | 	
________|________|________|________|________|________|
1       | 0	 | 	0 |P(1,2,3)|P(1,3,4)| ....   | 	
	|        |        |        | +T(1,3)|        |
	|        |        |        | +T(2,4)|        |
________|________|________|________|________|________|
        |        |        |        |        |P(1,4,5)|
    2   | 0	 | 	0 | 0	   |P(2,3,4)| +T(2,3)| 	
	|        |        |        |        | +T(3,5)|
________|________|________|________|________|________|
    3   | 	0| 	0 | 0	   | 	0   |P(3,4,5)| 	
	|        |        |        |        |        |
________|________|________|________|________|________|
    4   |0 	 |	  | 	   | 	    |        |
________|________|________|________|________|________|
     5  |0       | 	  |  	   |  	    |   0    | 	
________|________|________|________|________|________|

Implementare: 

//O(N^3)

	for (int j=1;j<=N;++j)
	{
		T[j][j]=0;
		T[j][j+1]=0;
	}
	for (int i=1;i<=N-2;++i)
		T[i][i+2]=P(i,i+1,i+2);
	for (int j=4;j<=N;++j)
		for (int i=j-3;i>=0;--j)
		{
			t[i][j]=oo;
			for (int vf=i+1;v<=j-1;++vf)
				if (P(i,vf,j)+T[i][vf]+T[vf][j]<t[i][j])
					t[i][j]= P(i,vf,j)+T[i][vf]+T[vf][j];
		}
 
** Numar minim de palindroame ale unui sir **

-abordarea este ca si mai sus , astfel A[i][j]= (C[x]==C[y] && A[x-1][y-1]==1 ) ? 1 : min ( valori ) 
, valori insemand toate numerele luate pe directiile jos-sus si dr-st ca mai sus 

  x y x y y x x y y y 
x 1 2|1|2 2 3 3 3 2|3|
y 0 1 2 1 2 2 3 2 3 3
x 0 0 1 2 2 1 2 3 2 3 
y 0 0 0 1 1 2 2 2|1|2|
y 0 0 0 0 1 2 2 1 2 2 
x 0 0 0 0 0 1 1 2 2 2
x 0 0 0 0 0 0 1 2 2 2 
y 0 0 0 0 0 0 0 1 1 1 
y 0 0 0 0 0 0 0 0 1 1
y 0 0 0 0 0 0 0 0 0|1|

Subproblema: Generarea primei solutii.
Vom aborda "invers" problema , adica de la matricea facuta mai sus vom parcurge valorile in sens invers. 
( st-dr si sus-jos )
